//给定一个长度为 n 的整数数组 height 。有 n 条垂线，第 i 条线的两个端点是 (i, 0) 和 (i, height[i]) 。 
//
// 找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。 
//
// 返回容器可以储存的最大水量。 
//
// 说明：你不能倾斜容器。 
//
// 
//
// 示例 1： 
//
// 
//
// 
//输入：[1,8,6,2,5,4,8,3,7]
//输出：49 
//解释：图中垂直线代表输入数组 [1,8,6,2,5,4,8,3,7]。在此情况下，容器能够容纳水（表示为蓝色部分）的最大值为 49。 
//
// 示例 2： 
//
// 
//输入：height = [1,1]
//输出：1
// 
//
// 
//
// 提示： 
//
// 
// n == height.length 
// 2 <= n <= 10⁵ 
// 0 <= height[i] <= 10⁴ 
// 
// Related Topics 贪心 数组 双指针 👍 3192 👎 0

package com.cute.leetcode.editor.cn;
public class ContainerWithMostWater {
    public static void main(String[] args) {
        int[] height = {1,3,2,5,25,24,5};
        new ContainerWithMostWater().new Solution().maxArea(height);
    }
    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        /**
         * 寻找围成面积的最大值
         * 使用双指针，两个板能承载的水由两板间距离以及短板长度决定
         * 每次向内收缩时，板间距必定减小
         * 移动短板时，新板长度可能比短板大也可能小，所以更新后新的ij间短板长度可能变大，盛水量可能变大
         * 如果移动长板，新板长度>长板时更新后短板长度依旧和之前一样；
         *  新板长度<长板，那么更新后短板长度变小；所以移动长板后盛水量必然减小
         */
        public int maxArea(int[] height) {
            int left = 0;
            int right = height.length - 1;
            int res = 0;
            while (left < right){// 优美的三目运算符
                res = height[left] < height[right] ?
                        Math.max(res, (right - left) * height[left++]) :
                        Math.max(res, (right - left) * height[right--]);

            }
            return res;
        }
    }
//leetcode submit region end(Prohibit modification and deletion)

}